package linear_list.leetcode.medium;

/**
 * @author bruin_du
 * @description 排序的循环链表
 * @date 2022/8/11 13:56
 **/
public class OfferII029_Insert {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            Node node = new Node(insertVal);
            node.next = node;
            return node;
        }
        Node minNode = head,maxNode = head, cur = head.next;
        //找到最小结点和最大结点
        while (cur != head) {
            if (cur.val <= minNode.val) {
                minNode = cur;
            }
            if (cur.val >= maxNode.val){
                maxNode = cur;
            }
            cur = cur.next;
        }
        Node prev = minNode;
        cur = minNode.next;
        // 遍历一圈中,如果发现满足条件的结点, 就插入
        // 否则就是在最大结点和最小结点之间插入!!!
        while (cur != minNode) {
            if (prev.val <= insertVal && insertVal <= cur.val) {
                Node node = new Node(insertVal, cur);
                prev.next = node;
                return head;
            }
            prev = cur;
            cur = cur.next;
        }
        Node node = new Node(insertVal, maxNode.next);
        maxNode.next = node;
        return head;
    }
    static class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }

    public static void main(String[] args) {
        Node node3 = new Node(3);
        Node node4 = new Node(3, node3);
        Node node5 = new Node(3, node4);
        Node node1 = new Node(5, node5);
        Node node2 = new Node(4, node1);
        Node head = new Node(3, node2);
        node3.next = head;
        OfferII029_Insert offer = new OfferII029_Insert();
        offer.insert(head, 2);
    }
}
